GATE CSE 2013
Q21.
Relation R has eight attributes ABCDEFGH. Fields of R contain only atomic values. F=\{CH\rightarrow G, A\rightarrow BC,B\rightarrow CFH,E\rightarrow A,F\rightarrow EG\} is a set of functional dependencies (FDs) so that F^{+} is exactly the set of FDs that hold for R. The relation R isQ22.
Consider the following sequence of micro-operations. MBR \leftarrow PC MAR \leftarrow X PC \leftarrow Y Memory \leftarrow MBR Which one of the following is a possible operation performed by this sequence?Q23.
Consider the following two sets of LR(1) items of an LR(1) grammar. \begin{array}{l|l} X \rightarrow c.X, c∕d &X → c.X, \$\\ X \rightarrow .cX, c∕ d& X → .cX, \$\\ X \rightarrow .d, c∕ d & X → .d, \$ \end{array} Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE? 1. Cannot be merged since look aheads are different. 2. Can be merged but will result in S-R conflict. 3. Can be merged but will result in R-R conflict. 4. Cannot be merged since goto on c will lead to two different sets.Q24.
What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production (i.e., of type A\rightarrow \epsilon and A \rightarrow a ) to parse a string with n tokens?Q25.
Consider an instruction pipeline with five stages without any branch prediction: Fetch Instruction (FI), Decode Instruction (DI), Fetch Operand (FO), Execute Instruction (EI) and Write Operand (WO). The stage delays for FI, DI, FO, EI and WO are 5 ns, 7 ns, 10 ns, 8 ns and 6 ns, respectively. There are intermediate storage buffers after each stage and the delay of each buffer is 1 ns. A program consisting of 12 instructions I1, I2, I3,..., I12 is executed in this pipelined processor. Instruction I4 is the only branch instruction and its branch target is I9. If the branch is taken during the execution of this program, the time (in ns) needed to complete the program isQ26.
Function f is known at the following points: The value of \int_{0}^{3}f(x)dx computed using the trapezoidal rule isQ27.
Suppose p is the number of cars per minute passing through a certain road junction between 5 PM and 6 PM, and p has a Poisson distribution with mean 3. What is the probability of observing fewer than 3 cars during any given minute in this interval?Q28.
A shared variable x, initialized to zero, is operated on by four concurrent processes W, X, Y, Z as follows. Each of the processes W and X reads x from memory, increments by one, stores it to memory, and then terminates. Each of the processes Y and Z reads x from memory, decrements by two, stores it to memory, and then terminates. Each process before reading x invokes the P operation (i.e., wait) on a counting semaphore S and invokes the V operation (i.e., signal) on the semaphore S after storing x to memory. Semaphore S is initialized to two. What is the maximum possible value of x after all processes complete execution?Q29.
A certain computation generates two arrays a and b such that a[i]=f(i)for o\leq i \lt n and b[i] = g (a[i] )for o\leq i \lt n. Suppose this computation is decomposed into two concurrent processes X and Y such that X computes the array a and Y computes the array b. The processes employ two binary semaphores R and S, both initialized to zero. The array a is shared by the two processes. The structures of the processes are shown below. Which one of the following represents the CORRECT implementations of ExitX and EntryY?Q30.
Three concurrent processes X, Y, and Z execute three different code segments that access and update certain shared variables. Process X executes the P operation (i.e., wait) on semaphores a, b and c; process Y executes the P operation on semaphores b, c and d; process Z executes the P operation on semaphores c, d, and a before entering the respective code segments. After completing the execution of its code segment, each process invokes the V operation (i.e., signal) on its three semaphores. All semaphores are binary semaphores initialized to one. Which one of the following represents a deadlock-free order of invoking the P operations by the processes?